A trend in modern microprocessor development is that the microprocessors are much faster than attached storage devices delivering the respective data the processor requires for operation. In order to prevent lack of data, fast and small memories ‘caches’ have been developed. These caches are used to acquire data from slower storage devices and store data to enable fast access by the microprocessor. This reduces the average microprocessor access time to the required data and increases the computer system performance.
However, the difficulty for a computer system is to predict which data will be needed in future microprocessor operations. Since the cache has only a limited size, only a limited amount of data can be preloaded into the cache. In order to efficiently control data flow to and from the cache, several strategies for cache management have been developed.
A common data replacement policy which determines which data can be discarded from the cache is the Least-Recently-Used (LRU) policy. The LRU policy is typically based on removing data in the cache that have least recently been requested or that are not often been requested, or a combination of both. Another strategy for cache management is predictive caching of data. For example for database applications, predictive caching utilizes certain algorithms to predict future data read requests. This comprehends recognition and learning of access patterns and detection of related access requests. The database system can use this information to preload data which is predicted to be used in the future. This reduces waiting times for data which are needed by an application or by the microprocessor for further processing.
U.S. Pat. No. 5,305,389 (Mark L. Palmer et al.) discloses a predictive cache system. Prefetches to a cache are made from predictions which are based on access patterns generated from prior accesses of a data processing system. During a training sequence, access patterns are generated and stored in a pattern memory. Also, access patterns generated from prior accesses of the data processing system are stored in the pattern memory. A predictor analyzes a current access pattern to predict from the similar access patterns stored in the pattern memory possible accesses to objects. Predicted objects are then prefetched to be stored in a cache memory. A cache memory subsystem evicts objects from the cache memory by order of priority, with most recent objects being assigned high priority to remain in the cache relative to other objects in the cache.
The problem with predictive caching is that prefetching of predicted objects for storage in a cache memory might be impossible, if the cache memory is not featuring the necessary control structures or data or if the free cache memory is not big enough to accept the prefetched object. Since cache resizing can cause long response times, incoming prefetching requests can be delayed which slows down the overall database system performance.